package demo2;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public int maxSubArray(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n + 1];

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }


    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length, sum = 0;
        for(int x : nums) { sum += x;}

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int fMax = Integer.MIN_VALUE, gMin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(nums[i - 1], f[i - 1] + nums[i - 1]);
            fMax = Math.max(fMax, f[i]);
            g[i] = Math.min(nums[i - 1], g[i - 1] + nums[i - 1]);
            gMin = Math.min(gMin, g[i]);
        }

        return sum == gMin ? fMax : Math.max(fMax, sum - gMin);
    }


    public int maxProduct(int[] nums) {
        int n = nums.length;

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = g[0] = 1;

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            int x = nums[i - 1], y = nums[i - 1] * f[i - 1], k = nums[i - 1] * g[i - 1];
            f[i] = Math.max(x, Math.max(y, k));
            g[i] = Math.min(x, Math.min(y, k));
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }


    public int getMaxLen(int[] nums) {
        int n = nums.length;

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            if(nums[i - 1] > 0){
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }else if(nums[i - 1] < 0){
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }


    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(n == 1 || n == 2) { return 0;}

        int[] dp = new int[n + 1];
        int ret = 0;
        for(int i = 3; i <= n; i++){
            if(nums[i - 1] - nums[i - 2] == nums[i - 2] - nums[i - 3]){
                dp[i] = dp[i - 1] + 1;
            }
            ret += dp[i];
        }
        return ret;
    }


    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;

        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i < n; i++){
            f[i] = 1;
            g[i] = 1;
        }

        int ret = 1;
        for(int i = 1; i < n; i++){
            if(arr[i] - arr[i - 1] > 0) { f[i] = g[i - 1] + 1;}
            if(arr[i] - arr[i - 1] < 0) { g[i] = f[i - 1] + 1;}
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
    public int maxTurbulenceSize2(int[] arr) {
        int n = arr.length;

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        for(int i = 0; i <= n; i++){
            f[i] = 1;
            g[i] = 1;
        }

        int ret = 1;
        for(int i = 2; i <= n; i++){
            if(arr[i - 1] - arr[i - 2] > 0) { f[i] = g[i - 1] + 1;}
            if(arr[i - 1] - arr[i - 2] < 0) { g[i] = f[i - 1] + 1;}
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }


    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> hash = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        s = " " + s;

        for(int i = 1; i <= n; i++){
            for(int j = i; j >= 1; j--){
                if(dp[j - 1] && hash.contains(s.substring(j, i + 1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }


    public int findSubstringInWraproundString(String s) {
        int n = s.length();

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) - s.charAt(i - 1) == 1 || (s.charAt(i) == 'a' && s.charAt(i - 1) == 'z')) {
                dp[i] += dp[i - 1];
            }
        }
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            hash[s.charAt(i) - 'a'] = Math.max(hash[s.charAt(i) - 'a'], dp[i]);
        }
        int sum = 0;
        for (int x : hash) {
            sum += x;
        }
        return sum;
    }
}
